package com.cty.C_SortAlgorithms.G_HeapSort;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/18 14:41
 * @Description:
 * @version: 1.0
 */
public class HeapArray {
    private int maxSize;
    private DataItem[] array;
    private int nItems;

    public HeapArray(int maxSize){
        this.maxSize = maxSize;
        array = new DataItem[maxSize];
        nItems = 0;
    }

    public boolean isEmpty(){
        return (nItems == 0);
    }

    public boolean isFull(){
        return (nItems == maxSize);
    }

    public int size(){
        return nItems;
    }

    public void displayArray(){
        for(int i=0; i<nItems; i++)
            System.out.print(array[i].getKey() + " ");
        System.out.println();
    }

    /**
     * 插入  O(logN)
     *      尾部插入，向上筛选
     * @param item
     * @return
     */
    public boolean insert(DataItem item){
        if(isFull())
            return false;

        array[nItems] = item;
        trickleDown(nItems++);
        return true;
    }  // end insert()

    /**
     * 删除  O(logN)
     *      头部删除，向下筛选
     * @return
     */
    public DataItem remove(){
        if(isEmpty())
            return null;

        DataItem temp = array[0];  // 记录原来最大值的索引
        array[0] = array[--nItems];  // 将尾部数据移到头部
        trickleDown(0);
        return temp;
    }  // end remove()

    /**
     * 改变指定索引位置处数据的关键字值
     * @param index
     * @param newKey
     * @return
     */
    public boolean change(int index, long newKey){
        if(index<0 || index>=nItems)
            return false;

        long oldKey = array[index].getKey();
        array[index].setKey(newKey);

        if(newKey > oldKey)
            trickleUp(index);
        else
            trickleDown(index);
        return true;
    }  // end change()

    /**
     * 向上筛选
     * @param index
     */
    private void trickleUp(int index){
        DataItem temp = array[index];  // 记录待交换数据
        int parent = (index - 1) / 2;  // 初始父节点

        while(index>0 && temp.getKey()>array[parent].getKey()){
            array[index] = array[parent];  // 父节点下移
            index = parent;  // 更新当前节点
            parent = (index - 1) / 2;  // 更新父节点
        }
        array[index] = temp;
    }  // end trickleUp()

    /**
     * 向下筛选
     * @param index
     */
    private void trickleDown(int index){
        DataItem temp = array[index];
        int largeChild;

        while(index < nItems/2){  // 保证至少有一个左子节点
            // 计算子节点索引
            int leftChild = 2*index + 1;
            int rightChild = leftChild + 1;

            // 选关键字最大的子节点
            if(rightChild<nItems && array[rightChild].getKey()>array[leftChild].getKey())
                largeChild = rightChild;
            else
                largeChild = leftChild;

            // 当待交换节点关键字大于等于最大子节点关键字，结束
            if(temp.getKey() >= array[largeChild].getKey())
                break;
            // 否则，更新循环条件
            array[index] = array[largeChild];  // 最大子节点上移
            index = largeChild;
        }  // end while
        array[index] = temp;
    }  // end trickleDown()


    /**
     * 获取无序数组
     * @param array
     */
    public void setArray(DataItem[] array){
        this.array = array;
        nItems = array.length;
    }

    /**
     * 堆排序
     *      平均时间复杂度：  O(N*logN)    受数据分布影响较小
     *      最好情况：        O(N*logN)
     *      最坏情况：        O(N*logN)
     *      空间复杂度：      O(1)         递归造成栈空间的使用
     *      排序方式：                     内部排序
     *      稳定性：                       不稳定          存在跳跃式交换
     * 分析：
     *      将无序数组转化为堆
     *          (N/2)-1 次向下筛选，筛选过程中比较和移动的次数相同，每次筛选比较和移动的次数都小于等于 log2(N)+1 （绝大部分小于）
     *          比较次数：[(N/2)-1]*[log2(N)+1]
     *          移动次数：[(N/2)-1]*[log2(N)+1]
     *      堆排序
     *          N-1 次移除最大值并伴随着 N-1 次向下筛选，筛选过程中比较和移动的次数相同，每次筛选比较和移动的次数都小于等于 log2(N)+1 （绝大部分小于）
     *          比较次数：(N-1)*[log2(N)+1]
     *          移动次数：(N-1)*[log2(N)+1]
     */
    public void heapSort(){
        int num = nItems;
        // 将无序数组转化为堆
        int i;
        for(i=nItems/2-1; i>=0; i--)
            trickleDown(i);

        // 堆排序
        for(i=nItems-1; i>0; i--){  // 最后一个数据没必要处理
            DataItem maxItem = remove();  // 移除最大值
            array[i] = maxItem;
        }

        // 显示排序后数据
        for(i=0; i<num; i++)
            System.out.print(array[i].getKey() + " ");
        System.out.println();
    }  // end HeapSort()


}  // end Heap{}
